\section*{Analysis}

In this section, we present the trade-offs of using heterogeneous seeds with
different thresholds $\tau$ and different maximum lengths $L_{max}$.

\begin{figure}[h]
\centering
\includegraphics[width=0.7\textwidth]{figures/Mapping_Memory_vs_tau_B.pdf}
\caption{The reduction in mapping cost and the increase in memory consumption of
the heterogeneous seeds with smaller threshold $\tau$, while $L_{max}=24$.}
\label{fig:tau}
\end{figure}


With a smaller $\tau$, more short seeds are tagged as expensive seeds and many
long cheap seeds are further extended into even longer cheaper seeds. As a
consequence, the memory consumption of heterogeneous seeds increases while
the total mapping cost decreases as $\tau$ increases, as shown in
Figure~\ref{fig:tau}.

\begin{figure}[h]
\centering
\includegraphics[width=0.7\textwidth]{figures/Mapping_Memory_vs_Lmax_B.pdf}
\caption{The reduction in mapping cost and the increase in memory consumption of
the heterogeneous seeds with larger maximum seed length $L_{max}$, while
$\tau=100$.}
\label{fig:maxLV}
\end{figure}

Similarly, with a longer maximum seed length $L_{max}$, long expensive seeds,
seeds which still have more than $\tau$ locations at the length of original
limit $L_{max}$, can be further extended into more longer seeds. As a
consequence, the memory consumption of heterogeneous seeds increases while the
total mapping cost of decreases as $L_{max}$ increases, as shown in
Figure~\ref{fig:maxLV}.

\begin{figure}[h]
\centering
\includegraphics[width=0.7\textwidth]{figures/Workload_tau_Lmax_B.pdf}
\caption{The reduction in the number of read verifications and the increase in the
number of extension verifications with smaller $\tau$ and larger $L_{max}$, when
mapping 1 million reads to human chromosome 1, under the requirement of
tolerating 5 errors.}
\label{fig:mappingwithHet}
\end{figure}

As $\tau$ becomes smaller and $L_{max}$ becomes longer, seeds also become longer
and cheaper. As a result, a read can now be partitioned into fewer longer seeds.
When high error-tolerance is desired, as more seeds are required, jigsaw seeds
become less successful and overlapping seeds are used more frequently.  This
leads to fewer full-scale read verifications but more extension verifications,
as Figure~\ref{fig:mappingwithHet} shows. Although extension verifications
involve much less computation than full-scale read verifications, with rapid
growth, the increase in the computation of extensions verifications may still
cancel out the benefit of the small reduction in the number of read
verifications.

While the optimal values of $\tau$ and $L_{max}$ for heterogeneous seeds depend
on the configuration of the computer, the desired error-tolerance of the mapper
and the reads to be mapped, it is beyond the scope of this paper to formulate
their relationships and to provide an optimal solution.
